package com.jhy.review.leetcode;

/**
 * 平衡二叉树
 * （1）它是一棵空树或它的左右两个子树的高度差的绝对值不超过1；
 * （2）平衡二叉树的左右两个子树都是一棵平衡二叉树。
 * 2022年7月23日22:37:09
 */
public class code03_BalanceBinaryTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static class ReturnBBType {
        public boolean isBalance;
        public int height;

        // 结构体
        public ReturnBBType(boolean isBalance, int height) {
            /**
             * 左子树 需要平衡(平的 高度)
             * 右子树 需要平衡(平的 高度)
             * 左树和右树要求是一样的
             * |左高-右高| <= 1;
             */
            this.isBalance = isBalance;
            this.height = height;
        }

        public ReturnBBType() {
        }
    }

    public static ReturnBBType process(TreeNode root) {
        // base case 为空树的时候的放回值
        if (root == null) {
            return new ReturnBBType(true, 0);
        }

        // 左树可以返回左树的两个信息
        // 右树可以放回两个信息 用了黑盒 在自己的题里面成功把黑盒拆掉
        ReturnBBType lData = process(root.left);
        ReturnBBType rData = process(root.right);

        // 接下来我也要放回两个信息 整个递归要连起来。解决root也要返回两个值
        // 根据左边的信息和右边的信息 返回我的信息
        int height = Math.max(lData.height, rData.height);

        boolean isBanlance = lData.isBalance && rData.isBalance
                && Math.abs(lData.height - rData.height) < 2;
        // 以root为头的整个树是否为平的 高度为多少
        return new ReturnBBType(isBanlance, height);
    }

    public static boolean isBalanced(TreeNode root) {
        ReturnBBType process = process(root);
        // 主函数调是否为平衡树整个信息
        return process.isBalance;

    }


}
